#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include "noise/noise.h"

#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))


typedef unsigned int uint;
typedef unsigned char uchar;
struct Drop
{
	int x, y;
	bool alive;
};

inline uchar getR(uint pixel)
{
   return static_cast<uchar>((pixel >> 16) & 0xFF);
}

inline uchar getG(uint pixel)
{
   return static_cast<uchar>((pixel >> 8) & 0xFF);
}

inline uchar getB(uint pixel)
{
   return static_cast<uchar>(pixel & 0xFF);
}

inline uint pack_rgb(int r, int g, int b)
{
   return ((r & 0xFF) << 16) + ((g & 0xFF) << 8) + (b & 0xFF);
}

inline uint* copyImage(uint *image, int width, int height)
{
   uint *newPic = new uint[width * height];
   memcpy(newPic, image, width * height * sizeof(uint));
   return newPic;
}

inline void copyImageData(float *to, const float *from, int width, int height)
{
	memcpy(to, from, width * height * sizeof(float));
}

inline uchar cap(double val)
{
   return static_cast<uchar>((val < 0.0) ? 0.0 : (val > 255.0) ? 255.0 : val);
}

inline int roundPowerOfTwo(int v)
{
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v++;
	return v;
}

uchar* copyHeightImage(uchar *image, int width, int height)
{
   uchar *newPic = new uchar[width * height];
   memcpy(newPic, image, width * height * sizeof(uchar));
   return newPic;
}

void copyImageData(uchar *to, const uchar *from, int width, int height)
{
   memcpy(to, from, width * height * sizeof(uchar));
}

void writeBMPHeader(int width, int height, FILE *outFile)
{
   //magic BM header
   char magicIdent[] = {0x42, 0x4D};
   fwrite(magicIdent, 1, 2, outFile);

   //file size
   uint offset = 14 + 40 + 0; //BMP Header + DIB Header + Palette
   uint rowsize = 4 * static_cast<uint>(floor(static_cast<double>((24 * width) + 31) / 32.0));
   uint fileSize = offset + rowsize * height;//BMP Header + DIB Header + Palette + Bitmap Data
   fwrite(&fileSize, 4, 1, outFile);

   //reserved (2 * 2)
   uint spacing = 0;
   fwrite(&spacing, 4, 1, outFile);

   //data offset
   fwrite(&offset, 4, 1, outFile);
}

void writeDIBHeader(int width, int height, FILE *outFile)
{
   //header size
   uint headerSize = 40;
   fwrite(&headerSize, 4, 1, outFile);

   //width & height of image
   fwrite(&width, 4, 1, outFile);
   fwrite(&height, 4, 1, outFile);

   //leave as 1
   short colorPlanes = 1;
   fwrite(&colorPlanes, 2, 1, outFile);

   //bits per pixel
   short bitsPerPixel = 24;
   fwrite(&bitsPerPixel, 2, 1, outFile);

   //compression method
   uint compressionMethod = 0; //no compression
   fwrite(&compressionMethod, 4, 1, outFile);

   //image size (just bitmap data)
   uint rowsize = 4 * static_cast<uint>(floor(static_cast<double>((24 * width) + 31) / 32.0));
   uint imageSize = rowsize * height;
   fwrite(&imageSize, 4, 1, outFile);

   //horizontal and vertical resolution in pixel per meter
   int resolution = 3780; //3780 = default mspaint value
   fwrite(&resolution, 4, 1, outFile);
   fwrite(&resolution, 4, 1, outFile);

   //number of colors in the palette
   uint numPaletteEntries = 0;
   fwrite(&numPaletteEntries, 4, 1, outFile);

   //number of important colors used
   uint numImportantColors = 0;
   fwrite(&numImportantColors, 4, 1, outFile);
}

bool writeBitmap(uint *image, int width, int height, const char *filename)
{
   //open file safely
   FILE *outFile = NULL;
   fopen_s(&outFile, filename, "wb");
   if(!outFile)
      return false;

   //write BMP header
   writeBMPHeader(width, height, outFile);

   //write DIB header
   writeDIBHeader(width, height, outFile);

   //write RGB data
   unsigned char zeroBuffer[4] = {0};
   const unsigned int align = (4 - (3 * width) % 4) % 4;
   unsigned int *pos = image + ((height - 1) * width);
   int doubleWidth = 2 * width;
   for(int y = 0; y < height; ++y, pos -= doubleWidth)
   {
      for(int x = 0; x < width; ++x, ++pos)
      {
         fputc(getB(*pos), outFile);
         fputc(getG(*pos), outFile);
         fputc(getR(*pos), outFile);
      }
      fwrite(zeroBuffer, 1, align, outFile);
   }

   //close the file
   fclose(outFile);

   //success
   return true;
}

float* generateBaseTerrain(int width, int height)
{
	noise::module::Perlin perlinModule;
	float *image = new float[width * height];
	float *iter = image;
	for(int y = 0; y < width; ++y)
	{
		for(int x = 0; x < height; ++x, ++iter)
		{
			*iter = (1.0f + static_cast<float>(perlinModule.GetValue(static_cast<double>(x) / width, static_cast<double>(y) / height, 1234.5))) / 2.0f;
		}
	}
	return image;
}

void writeTerrain(float *heightMap, int width, int height, char *filename)
{
	uint *image = new uint[width * height];
	uint *pixel = image;
	float *hpix = heightMap;
	uchar capped;
	for(int i = 0; i < width * height; ++i, ++pixel, ++hpix)
	{
		capped = static_cast<uchar>(MAX(MIN(*hpix, 1.0f), 0.0f) * 255.0f);
		*pixel = pack_rgb(capped, capped, capped);
	}
	writeBitmap(image, width, height, filename);
	delete[] image;
}

Drop updateDrop(Drop* drop)
{

	int minh;
	//find min of 8-connected
	if(*(dropsPos - (width + 1)) < minh)
	{
		minh = *(dropsPos - (width + 1));
		minx = drops[i].x - 1;
		miny = drops[i].y - 1;
	}
	if(*(dropsPos - width) < minh)
	{
		minh = *(dropsPos - width);
		minx = drops[i].x;
		miny = drops[i].y - 1;
	}
	if(*(dropsPos - (width - 1)) < minh)
	{
		minh = *(dropsPos - (width - 1));
		minx = drops[i].x + 1;
		miny = drops[i].y - 1;
	}
	if(*(dropsPos - 1) < minh)
	{
		minh = *(dropsPos - 1);
		minx = drops[i].x - 1;
		miny = drops[i].y;
	}
	if(*(dropsPos + 1) < minh)
	{
		minh = *(dropsPos + 1);
		minx = drops[i].x + 1;
		miny = drops[i].y;
	}
	if(*(dropsPos + width - 1) < minh)
	{
		minh = *(dropsPos + width - 1);
		minx = drops[i].x - 1;
		miny = drops[i].y + 1;
	}
	if(*(dropsPos + width) < minh)
	{
		minh = *(dropsPos + width);
		minx = drops[i].x;
		miny = drops[i].y + 1;
	}
	if(*(dropsPos + width + 1) < minh)
	{
		minh = *(dropsPos + width + 1);
		minx = drops[i].x + 1;
		miny = drops[i].y + 1;
	}

}

void erodeHelper(float *heightMap, int width, int height, int numDrops)
{

	Drop *drops = new Drop[numDrops];
	int numAliveDrops = numDrops;

	//initialize drops with random starting positions
	for(int i = 0; i < numDrops; ++i)
	{
		drops[i].x = abs(rand()) % width;
		drops[i].y = abs(rand()) % height;
		drops[i].alive = true;
	}

	//iterate
	while(numAliveDrops > 0)
	{
		for(int i = 0; i < numDrops; ++i)
		{
			if(drops[i].alive)
			{
				int minx = drops[i].x;
				int miny = drops[i].y;
				int minh = heightMap[minx + miny * width];

				uchar *dropsPos = heightMap + minx + miny * width;

				//drop down space
				if(*dropsPos > 0)
					*dropsPos -= 1;

				//edge means done
				if((drops[i].y <= 0) || (drops[i].y >= height - 1) || (drops[i].x <= 0) || (drops[i].x >= width - 1))
				{
					drops[i].alive = false;
					numAliveDrops--;
					continue;
				}


				//if don't move, it's dead
				if((minx == drops[i].x) && (miny == drops[i].y))
				{
					drops[i].alive = false;
					numAliveDrops--;
					continue;
				}

				//move drop
				drops[i].x = minx;
				drops[i].y = miny;
			}
		}
	}

	delete[] drops;
}

void erode(float *heightMap, int width, int height, int iterations, int numDrops)
{
	for(int i = 0; i < iterations; ++i)
	{
		erodeHelper(heightMap, width, height, numDrops);
	}
}

void erodeMorph(float *heightMap, int width, int height, int iterations)
{
	for(int i = 0; i < iterations; ++i)
	{
		float *newMap = new float[width * height];
		for(int y = 0; y < height; ++y)
		{
			for(int x = 0; x < width; ++x)
			{
				float min = heightMap[x + y * width];
				if(x > 0)
				{
					min = MIN(min, heightMap[x + y * width - 1]);
				}
				if(x < width - 1)
				{
					min = MIN(min, heightMap[x + y * width + 1]);
				}
				if(y > 0)
				{
					min = MIN(min, heightMap[x + (y - 1) * width]);
				}
				if(y < height - 1)
				{
					min = MIN(min, heightMap[x + (y + 1) * width]);
				}
				newMap[x + y * width] = min;
			}
		}
		copyImageData(heightMap, newMap, width, height);
		delete[] newMap;
	}
}

int main(int argc, char *argv[])
{
	if(argc != 3)
	{
		printf("Syntax: terrain size terrain_destination.bmp\n");
		char a;
		scanf("%s", &a);
		return 1;
	}

	int size = roundPowerOfTwo(atoi(argv[1]));
	float *image = NULL;
	image = generateBaseTerrain(size, size);
	//meanFilter(image, size, size, 7);
	//contrast(image, size, size, 40);
	//erode(image, size, size, 2000, 400);
	erodeMorph(image, size, size, 10);
	writeTerrain(image, size, size, argv[2]);
	printf("Done!\n");
	return 0;
}
